Cyclic redundancy codes (CRC) have been used in various algorithms to ensure the integrity of data transmitted from a transmitting device or system to a receiving device or system. In general, CRC error detection is accomplished by encoding with transmitted data, a code representative of the remainder of an arithmetic carry-less division operation (i.e., modulo-2) between the transmitted code and a generator polynomial. The same generator polynomial may then be used at the receiver in another carry-less division operation on the transmitted data, the result of which can be compared to the remainder value encoded to detect any errors in the transmitted data.
One prior art technique for performing CRC error detection includes “table-based” algorithms, which replace one or more arithmetic operations involved in the carry-less division operations with a look-up operation within a table containing pre-calculated results of the one or more arithmetic operations. FIG. 1, for example, illustrates a prior art table-based CRC error detection algorithm, in which a 32 byte register contains the current value of the CRC code associated with a bit stream. The value stored within this register represents an increase of the data to be transmitted. Data may be augmented with the CRC code before transmission. When a new byte from the non-augmented portion of the data is used in the calculation of CRC, a Boolean “exclusive OR” (XOR) operation is performed between the new byte and the least significant byte of the register containing the current CRC value. The result of the XOR operation is used to index a table of 256 entries (4 bytes per entry, for example), which contain a pre-calculated result of a carry-less (e.g., modulo-2) division operation between the table index multiplied by the value, 232, and the generator polynomial. The bytes returned from this table lookup operation are then XOR-ed with the remaining bytes of the register holding the current CRC value which have not been taken into account (i.e., the 3 most significant bytes of the register). These bytes are shifted to the right by one byte position before the XOR operation takes place. The result of this XOR operation is the next CRC value to be used for augmenting the data and is kept in the same register as the old CRC value.
The operations discussed in regard to FIG. 1 require processing resources (e.g., cycle time and power) to compute, as well as numerous input/output and/or memory access operations within the computer systems in which the CRC algorithm is implemented. Further complicating the problem is the fact that many systems implementing CRC algorithms use bit reflection techniques within the transmitted data portions. More specifically, some CRC generation algorithms (e.g., “CRC32c”) reflect the bits inside their respective bytes before CRC code calculation. . Bit reflection is a process by which the bits of a binary data segment, such as a byte or a collection of bytes, switch positions in a mirrored fashion. For example, the reflected representation of “1010” is “0101”. Typically, a combination of bit reflection and the use of a specific addressing scheme in a processor (e.g., “little endian”) result in the bits of an input stream being stored in a order which is suitable for fast processing by a software CRC generation algorithm
Dealing with the reflected version of data introduces yet another layer of complexity and computational intensity to the prior art CRC algorithm illustrated in FIG. 1. In general, many prior art CRC algorithms, particularly those using table-based implementations, can require excessive hardware and/or software resources, as well as an increase of power required from the systems in which the algorithms are implemented.